方法简述

虽然不用建树，我还是建了一个，用的是顺序存储结构（数组）

char tree[501];

头文件

#include <iostream>
#include <memory.h>
#include <map>
using namespace std;

其中memory.h是为memset做准备的

建树

char tree[501];
map<char, int> k;

memset(tree, '*', 501);
int n;
cin>>n;
char a, b, c;
for(int i=0;i<n;i++)
{
    cin>>a>>b>>c;
    if(!i)
    {
        tree[1] = a;
        k[a] = 1;
    }
    k[b] = k[a] * 2;
    tree[k[b]] = b;
    k[c] = k[a] * 2 + 1;
    tree[k[c]] = c;
}

memset行用于给tree赋值。

听说第一行就是有关根节点的一行

if行用于判断是否为第一行，将根节点写入。k用于存字符出现的下标地址，方便查询一个节点的位置。

遍历

void DLR(int n)
{
    if(tree[n] == '*') return;
    cout<<tree[n];
    DLR(n*2);
    DLR(n*2+1);
}

还记得前文的memset吗？输入的空结点用*表示，所以方便起见把树初始化成*。如果遇到*，则代表该结点不存在，自然就可以退出那个结点了。

根据前序遍历的定义，写出递归函数即可。

程序

#include <iostream>
#include <memory.h>
#include <map>
using namespace std;

char tree[501];
map<char, int> k;

void DLR(int n)
{
    if(tree[n] == '*') return;
    cout<<tree[n];
    DLR(n*2);
    DLR(n*2+1);
}

int main()
{
    memset(tree, '*', 501);
    int n;
    cin>>n;
    char a, b, c;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        if(!i)
        {
            tree[1] = a;
            k[a] = 1;
        }
        k[b] = k[a] * 2;
        tree[k[b]] = b;
        k[c] = k[a] * 2 + 1;
        tree[k[c]] = c;
    }
    DLR(1);
    return 0;
}